从时间复杂度，空间复杂度，稳定性和初始状态等方面分析排序算法

时间复杂度

简单排序在已经排好序的情况下时间复杂度是最好的，在逆序的情况下是最坏的。

快速排序在基准元素是最小或最大值时是最坏的。

归并排序与堆排序是最稳定的。

##　空间复杂度

只有归并排序和快速排序需要额外的空间。

因为采用递归的方法，递归的次数是$O(logN)$。每一次递归都需要空间。

快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度$O(1)$。 但需要注意快速排序每次递归都会返回一个基准元素的下标位置，必须使用栈。递归栈上需要花费最少$logN$最多$N$的空间。

归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是$logN$，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是$O(N)$。

归并排序需要额外的$O(N)$的空间。

快速排序需要额外的$O(NlogN)$的空间。

稳定性

稳定排序：插入，冒泡，归并

不稳定排序：选择，快速，堆

归并排序：在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

堆排序：在叶子节点与父节点这3个元素之间的选择最大或最小不会破坏稳定性。但在叶子节点之上的节点交换会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

快速排序：在基准元素与有相同元素之间交换时会破坏稳定性。（５，３，９，３，８，１０）中基准元素５与第二个３交换。

选择排序：序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

初始状态

算法复杂度与数组的初试状态无关：

一堆（堆排序）乌龟（归并排序）选（选择排序）基（基数排序）友

元素总比较次数与初始状态无关的有：选择排序、基数排序。

元素总移动次数与初始状态无关的有：归并排序、基数排序